// 基本思想：将整个序列分为前i个有序序列和后n-i个无序序列，每一次排序，
// 将无序序列的第1个元素在有序序列中找到相对应的位置并插入

// 最佳时间复杂度：O(n)
// 最差时间复杂度：O(n^2)
// 排序稳定性：稳定
function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let temp = arr[i]
        let j = i
        // 从右到左遍历有序序列，和temp比较，直到找到合适的位置
        while (j > 0 && arr[j - 1] > temp) {
            // 将有序序列插入位置的元素依次右移一位
            arr[j] = arr[j - 1]
            j -= 1
        }
        arr[j] = temp
    }
    return arr
}
let arr = [6, 2, 3, 5, 1, 4]
console.log(insertSort(arr))